/**优先队列 (单调队列) - 会丢弃不符合条件的数据 */
export class PriorityQueue {
    /**单调队列  */
    queue: number[] = []
    /** 控制单调性
     * - true: 递减队列 - 队头是队列中最大的，从队头往队尾递减 
     * - false: 递增队列 - 队头是队列中最小的，从队头往队尾递增
     */
    #type: boolean
    /**优先队列 (单调队列) 构造函数
     * @param type 控制单调性  true递减、false递增  
     */
    constructor(type: boolean) {
        this.#type = type
    }
    /**入队 */
    enqueue(value: number) {
        // 如果是递减队列：若当前入队元素大于队尾，则会剔除所有比value小的队尾元素
        // 如果是递增队列：若当前入队元素小于队尾，则会剔除所有比value大的队尾元素
        if (this.#type) {
            while (value > this.queue[this.queue.length - 1]) {
                this.queue.pop()
            }
        } else {
            while (value < this.queue[this.queue.length - 1]) {
                this.queue.pop()
            }
        }
        this.queue.push(value)
        console.log(this.queue);
    }
    /**队头出队 */
    dequeue() {
        if (this.queue.length) {
            return this.queue.shift()
        }
    }
}
/**优先队列 (单调队列) - 所有数据都保留  (时间复杂度比较高) */
export class PriorityQueueAll {
    /**单调队列  */
    queue: number[] = []
    /** 控制单调性
     * - true: 递减队列 - 队头是队列中最大的，从队头往队尾递减 
     * - false: 递增队列 - 队头是队列中最小的，从队头往队尾递增
     */
    #type: boolean
    /**优先队列 (单调队列) 构造函数
     * @param type 控制单调性  true递减、false递增  
     */
    constructor(type: boolean) {
        this.#type = type
    }
    /**入队 */
    enqueue(value: number) {
        this.queue.push(value)
        this.queue.sort((a, b) => this.#type ? b - a : a - b)
        // console.log(this.queue);
    }
    /**队头出队 */
    dequeue() {
        if (this.queue.length) {
            return this.queue.shift()
        }
    }
}
/**LCP 30. 魔塔游戏 */
export function magicTower(nums: number[]): number {
    // 自己实现的优先队列比较草率，超时了，但是其它地方都是正确的思路 
    if (nums.reduce((p, c) => p + c) < 0) return -1
    let nowSum = 1//初始是一滴血
    let count = 0
    /**记录所有经过的怪物房间的单调队列 */
    const queue = new PriorityQueueAll(false)
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i]
        if (num < 0) queue.enqueue(num) //

        let tempSum = nowSum + num
        if (tempSum <= 0) {//血量不是正数就寄了
            const top = queue.dequeue()!
            tempSum -= top //把这个最大的出队，代表放在最后面了，所以当前的总和需要加上曾经被扣的血量 
            count++
        }
        nowSum = tempSum
    }

    return count
}
/**239. 滑动窗口最大值
 * - 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位
 * - 返回 滑动窗口中的最大值 。
 */
export function maxSlidingWindow(nums: number[], k: number): number[] {
    /**单调队列，队头是队列中最大的 */
    class MonoQueue {
        /**单调队列 从队头往队尾递减 */
        queue: number[] = []
        /**入队 */
        enqueue(value: number) {
            //思路，当你入队时，前面不能有比你大的
            //不断剔除掉队尾的比你小的人，再入队
            let back = this.queue[this.queue.length - 1]
            while (back !== undefined && value > back) {
                this.queue.pop()
                back = this.queue[this.queue.length - 1]
            }
            this.queue.push(value)
        }
        /**队头出队 */
        dequeue(value: number) {
            let top = this.top();
            if (top === value) {
                this.queue.shift();
            }
        }
        /**获取队头元素（最大的元素） */
        top() {
            return this.queue[0]
        }

    }
    const queue = new MonoQueue()
    const resArr: number[] = [];
    /**窗口左边界 */
    let slow = 0
    /**窗口右边界 */
    let fast = 0
    //第一步先把当前窗口进队
    while (fast < k) {
        queue.enqueue(nums[fast++]);
    }
    resArr.push(queue.top()) //结果数组放入当前窗口最大值
    while (fast < nums.length) {
        queue.enqueue(nums[fast++]);//新的进队
        queue.dequeue(nums[slow++]);//旧的出队
        resArr.push(queue.top()) //结果数组放入当前窗口最大值
    }
    return resArr
}